Corelab Seminar
2008-2009

Paris Koutris and Vassilis Sirgkanis (NTUA)
Gomory-Hu trees and applications

Abstract. Gomory-Hu (GH) trees encode optimally all the possible min-cuts between any two vertice of a graph. In this presentation we will describe an algorithm to construct such a tree in polynomial time and we will prove the correctness of it. Furthermore, we will present a GH-tree based approximation algorithm for the minimum k-cut problem. There will also be a demonstration of an implementation of the algorithm.

Material. Slides [pdf], source [zip].

References.

  1. Vazirani, Vijay. “Approximation Algorithms.” New York: Springer, 2003. (pages 40-46)
  2. R.E. Gomory, T.C.Hu Multi-terminal network flows. Journal of the SIAM, 9:551-570, 1961
  3. Dominique Barth, Pascal Berthome, Madiagne Diallo. On the analysis of Gomory-Hu cut-trees relationship, Research report LIMOS/RR-05-02